Cerca local iterativa[1][2] (en anglès, Iterated local search, ILS)[3] és un terme de Matemàtiques aplicades i de Ciències de la computació que defineix una modificació de cerca local o de mètodes hill climbing per solucionar problemes d'optimització discreta.
Els mètodes de cerca local poden quedar atrapats en un mínim local, o sigui un punt solució que és òptim en el seu entorn.
Una modificació senzilla consisteix a fer crides iterativament a la rutina de cerca local, cada cop començant des d'una configuració inicial diferent. Això s'anomena cerca local repetida, i implica que el coneixement obtingut durant les fases de cerca locals anteriors no és utilitzat. Aprendre implica que la història anterior, per exemple la memòria sobre els mínims locals trobats anteriorment, s'extreu per produir cada vegada punts de partida millors per a la cerca local.
S'assumeix implícitament que hi ha una distribució agrupada de mínims localsː quan es minimitza una funció, és més fàcil determinar bons mínims locals quan es comença des d'un mínim local amb un valor baix que quan es comença des d'un punt aleatori. L'única precaució és evitar el confinament en una conca d'atracció, de manera que el salt per transformar un òptim local en el punt de partida per a la següent iteració ha de ser adequat. Si el salt és massa curt no ens escaparem de la zona del mínim local i si és massa llarg, el procés esdevindria un procés amb reinicis aleatoris sense memòria.
La cerca local iterativa està basada en la construcció d'una seqüència de solucions locals òptimes:
La força de pertorbació ha de ser suficient per dirigir la trajectòria a una conca d'atracció diferent que condueixi a un òptim local diferent
El mètode ha estat aplicat a diversos problemes d'optimització combinatòria incloent -hi els problemes d'escalonament de processos,[4][5] els problemes de Flow-Shop,[3][6] els problemes d'enrutament de vehicles,[7] així com molts altres.
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search